/**
 *    Copyright (C) 2008, 2009 Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */

#ifndef _CUBEFS_CORE_BTREE_MODEL_INSERT_HPP
#define	_CUBEFS_CORE_BTREE_MODEL_INSERT_HPP

#include <cubefs/api/models/logs.hpp>
#include <cubefs/core/container/container.hpp>
#include <cubefs/core/btree/pages/tools.hpp>

#define CUBEFS_SOURCE "cubefs/core/btree/model/insert.hpp:" CUBEFS_AT

namespace cubefs    {
namespace ctr       {

using namespace cubefs::btree;

CUBEFS_MODEL_PART_BEGIN(InsertName)

    typedef typename Base::Types                                                Types;
    typedef typename Base::PageMgr                                              PageMgr;

    typedef typename Base::Page                                                 Page;
    typedef typename Base::ID                                                   ID;
    

    typedef typename Base::NodeBase                                             NodeBase;
    typedef typename Base::Counters                                             Counters;
    typedef typename Base::Iterator                                             Iterator;

    typedef typename Base::NodeDispatcher                                       NodeDispatcher;
    typedef typename Base::RootDispatcher                                       RootDispatcher;
    typedef typename Base::LeafDispatcher                                       LeafDispatcher;
    typedef typename Base::NonLeafDispatcher                                    NonLeafDispatcher;

    typedef typename Base::Node2RootMap                                         Node2RootMap;
    typedef typename Base::Root2NodeMap                                         Root2NodeMap;

    typedef typename Base::NodeFactory                                          NodeFactory;

    typedef typename Base::Key                                                  Key;
    typedef typename Base::Value                                                Value;

    static const Int Indexes                                                    = Base::Indexes;

    typedef typename Base::Metadata                                             Metadata;


    void create_new() {
        NodeBase *node = CreateNode(0, true, true);
        me_.set_root(node->id());
    }

    NodeBase *CreateNode(Short level, bool root, bool leaf)
    {
        CUBEFS_TRACE(me_, "CreateNode:", level, root, leaf, me_.name());
        
        NodeBase* node = NodeFactory::Create(me_.mgr(), level, root, leaf);

        if (root) {
            Metadata meta = me_.GetRootMetadata(node);
            meta.model_name() = me_.name();
            me_.SetRootMetadata(node, meta);
        }

        node->model_hash() = me_.hash();

        CUBEFS_TRACE(me_, "Node ID:", node, node->id(), node->id().value());

        return node;
    }

    void InsertSpace(NodeBase *node, Int from, Int count)
    {
        MoveElements<NodeDispatcher>(node, from, count);

        if (!node->is_leaf()) {
            MoveChildren<NonLeafDispatcher>(node, from, count, me_.mgr());
        }
    }

    
    NodeBase* SplitNode(NodeBase *one, NodeBase *parent, Int parent_idx, Int from, Int shift)
    {        
        CUBEFS_TRACE(me_, "SplitNode", one->id(), one->parent_idx(), "parent", parent->id(), parent_idx, "at", from, "shift", shift);

        NodeBase* two = CreateNode(one->level(), false, one->is_leaf()); // one->is_root() was false here
        
        Int count = CopyElements<NodeDispatcher>(one, two, from, shift);
        
        Counters counters;

        if (!two->is_leaf())
        {
            counters = AccumulateChildrenCounters<NonLeafDispatcher, Counters>(two, from, shift, count, me_.mgr());

            UpdateChildrenParentIdx<NonLeafDispatcher>(two, from, shift, count, me_.mgr());

            two->counters() += counters;
            one->counters() -= counters;
        }
        else
        {
            counters.page_count()           = 0;
            two->counters().page_count()    = 1;

            Int one_children_count = me_.GetChildrenCount(one);
            counters.key_count() = one->counters().key_count() - one_children_count;
            one->counters().key_count() = one_children_count;

            two->counters().key_count() = me_.GetChildrenCount(two);
        }

        two->parent_idx() = parent_idx;
        two->parent_id()  = parent->id();

        me_.PostSplit(one, two, from);

        NodeBase *one_parent = me_.GetParent(one);
        
        Key max[Indexes];
        me_.GetMaxKeys(one, max);

        me_.UpdateBTreeKeys(one_parent, one->parent_idx(), max);
        me_.SetINodeData(parent, parent_idx, &two->id());

        me_.GetMaxKeys(two, max);
        me_.UpdateBTreeKeys(parent, parent_idx, max);

        if (!(one_parent->id() == parent->id()))
        {
            me_.UpdateBTreeCounters(one_parent, -counters);
            me_.UpdateBTreeCounters(parent, Counters(counters.page_count() + 1, counters.key_count()));
        }
        else {
            me_.UpdateBTreeCounters(parent, Counters(1, 0));
        }

        return two;
    }


    NodeBase* SplitBTreeNode(NodeBase *page, Int count_leaf, Int shift)
    {
        NodeBase *parent = me_.GetParent(page);
        NodeBase *new_page;

        if (parent != NULL)
        {
            Int idx_in_parent = page->parent_idx();
            if (me_.GetCapacity(parent) == 0)
            {
                CUBEFS_TRACE(me_, "Parent", parent->id(), "is full", idx_in_parent, me_.GetChildrenCount(parent));
                Int parent_idx;

                if (idx_in_parent < me_.GetChildrenCount(parent) - 1)
                {
                    NodeBase *tmp = SplitBTreeNode(parent, idx_in_parent + 1, 1);
                    parent = tmp;
                    parent_idx = 0;
                }
                else
                {
                    parent = SplitBTreeNode(parent, me_.GetChildrenCount(parent) / 2, 0);
                    parent_idx = me_.GetChildrenCount(parent);
                    InsertSpace(parent, parent_idx, 1);
                }

                new_page = SplitNode(page, parent, parent_idx, count_leaf, shift);
            }
            else
            {
                CUBEFS_TRACE(me_, "Make room in parent", parent->id(), "at", idx_in_parent + 1);
                InsertSpace(parent, idx_in_parent + 1, 1);
                new_page = SplitNode(page, parent, idx_in_parent + 1, count_leaf, shift);
            }
        }
        else
        {
            NodeBase* root = me_.GetRoot();
            NodeBase* new_root = CreateNode(root->level() + 1, true, false);

            CUBEFS_TRACE(me_, "Split root", root->id(), "new root", new_root->id());

            me_.CopyRootMetadata(root, new_root);

            root = me_.Root2Node(root);

            new_root->parent_id() = root->parent_id();
            new_root->parent_idx() = 0;
            
            root->parent_id() = new_root->id();
            root->parent_idx() = 0;

            Key keys[Indexes];
            me_.GetMaxKeys(root, keys);
            me_.SetKeys(new_root, 0, keys);
            me_.SetINodeData(new_root, 0, &root->id());
            me_.SetChildrenCount(new_root, 2);

            new_root->counters() = root->counters();
            new_root->counters().page_count() += 1;

            me_.set_root(new_root->id());

            new_page = me_.SplitNode(page, new_root, 1, count_leaf, shift);

        }

        return new_page;
    }

    template <typename Keys, typename Data>
    class InsertFn {
        const Keys *keys_;
        const Data *data_;
    public:
        InsertFn(const Keys *keys, const Data *data): keys_(keys), data_(data) {}

        template <typename Node>
        void operator()(Node *node) {
            node->map().size() = 1;

            for (Int c = 0; c < Node::INDEXES; c++) {
                node->map().key(c, 0) = keys_[c];
            }

            node->map().data(0) = *data_;
            node->map().Reindex();
        }
    };


    void InsertEntry(Iterator &iter, const Key *keys, const Value &value) {
        CUBEFS_TRACE(me_, "InsertEntry", iter.page(), iter.key_idx(), iter.IsEof(), iter.IsEmpty(), keys[0]);

        if (iter.IsNotEmpty())
        {
            NodeBase *node = iter.page();
            Int idx = iter.key_idx();
            CUBEFS_TRACE(me_, "Insert value. idx =", idx);

            if (me_.GetCapacity(node) > 0)
            {
                CUBEFS_TRACE(me_, "Node", node, "has enough capacity");
                InsertSpace(node, idx, 1);
            }
            else if (idx == 0)
            {
                SplitBTreeNode(node, me_.GetChildrenCount(node) / 2, 0);
                idx = 0;
                InsertSpace(node, idx, 1);
            }
            else if (idx < me_.GetChildrenCount(node))
            {
                NodeBase *new_node = SplitBTreeNode(node, idx, 0);
                InsertSpace(node, idx, 1);
            }
            else {
                node = SplitBTreeNode(node, me_.GetChildrenCount(node) / 2, 0);
                
                idx = me_.GetChildrenCount(node);
                InsertSpace(node, idx, 1);

                iter.page() = node;
                iter.key_idx() = idx;
            }

            me_.SetLeafDataAndReindex(node, idx, keys, value);

            if (idx >= me_.GetChildrenCount(node) - 1) {
                me_.UpdateBTreeKeys(node);
            }

            me_.UpdateBTreeCounters(node, Counters(0, 1));
        }
        else
        {
            NodeBase *node = CreateNode(0, true, true);

            me_.set_root(node->id());
            iter.page() = node;
            iter.key_idx() = 0;
        
            InsertFn<Key, Value> fn(keys, &value);
            LeafDispatcher::Dispatch(node, fn);

            me_.UpdateBTreeCounters(node, Counters(0, 1));
        }

        iter.reset_state();
    }


    void InsertEntry(Iterator &iter, Key key, const Value &value) {
        Key keys[Indexes];

        for (Int c = 0; c < Indexes; c++)
        {
            keys[c] = key;
        }

        InsertEntry(iter, keys, value);
    }

    Iterator EmptyIterator() {
        return Iterator(me_);
    }

CUBEFS_MODEL_PART_END

} //ctr
} //cubefs

#undef CUBEFS_SOURCE

#endif	/* _CUBEFS_CORE_BTREE_MODEL_INSERT_HPP */
